package com.cfc.stage1;

import common.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 前序遍历
 *   https://leetcode.cn/problems/binary-tree-preorder-traversal/
 * @author: yangxuan10
 * @create: 2024-04-23 11:16
 **/
public class PreorderTraversal {

    /*
        先(根)序遍历（根左右）：A B D H E I C F J K G
        中(根)序遍历（左根右） : D H B E I A J F K C G
        后(根)序遍历（左右根） : H D I E B J K F G C A
    */

    @Test
    public void test1() {
        System.out.println(preorderTraversal(TreeNode.generateTree(1)));
        System.out.println(preorderTraversal(TreeNode.generateTree(2)));
    }

    public List<Integer> preorderTraversal(TreeNode treeNode) {
        List<Integer> list = new ArrayList<>();
        if (treeNode == null) {
            return list;
        }
        return preorderTraversal(list,treeNode);
    }

    /**
     *  前序遍历
     */
    public List<Integer> preorderTraversal(List<Integer> list, TreeNode treeNode) {
        list.add(treeNode.val);
        if (treeNode.left != null) {
            preorderTraversal(list, treeNode.left);
        }
        if (treeNode.right != null) {
            preorderTraversal(list, treeNode.right);
        }
        return list;
    }
}